二分图博弈

博弈论趣题

问题

有一个二分图，点带点权，分成A集合和B集合。两人轮流选点，每次只能选和上一次有连边的点（第一次从A集合任选），选到一个点把点权$-1$，点权为$0$的点不能再选。最后不能选者失败。求一个先手必胜策略或说明先手必败。

结论

先手应该选择一个不一定在最大匹配中的点。即存在一个最大匹配使得该点没有被匹配满。如果这样的点不存在则先手必败。

证明

对于任意一个最大匹配，首先选择一个不在该匹配中的点，对于对手选的每个点，我们都选择在匹配中和它对应的那个点。可以证明对手在任何时候都不能选择不在匹配中的点（否则把所有选过的点连起来是一条增广路，该匹配不是最大匹配），先手必胜。否则，如果先手选择了一个必定在最大匹配中的点，该点点权$-1$后最大匹配必然跟着$-1$，那么原来的最大匹配去掉了该点和B集合对应的点这组匹配后仍然是最大匹配。此时该对应点就是成为了不一定在最大匹配中的点，按照上面的证明后手必胜。（也可以用归纳法证明）

如何求这样的点

使用网络流求出最大匹配，然后在残余网络上dfs。记超级原点为$S$，超级汇点为$T$，则在$S$一侧的点中，$S$可达的就是不一定在最大匹配中的点。逆命题也成立。$T$一侧同理。

这个方法的证明

对于$S$一侧$S$可达的点$x$，若原图$S→x$边没有流满显然成立，否则沿着$S→\text{S到x的路径}→x→S$这条回路加流量，变化后的最大流中$S→x$边就没有流满。

例题（然而并没有地方提交）

小A和小B正在进行一场博弈，规则如下：开始时，有若干个正整数。游戏的第一步中小A先任选一个数删去，之后两个人轮流操作，每次选择一个数并删去。设当前选择的数为$x$，前一个选择的数为$y$，则$\frac{x}{y}$和$\frac{y}{x}$中必须有一个质数。无法操作者负。对于给定的初始数集，你需要确定：小A是否有必胜策略？如果有，小A在第一步中可以选择哪些数？

输入第一行为一个正整数$n$；接下来$n$行，每行两个正整数$p,q$，表示正整数$p$在一开始的数中出现了$q$次。

若小A没有必胜策略，输出-1；否则，升序输出小A第一步可以选择，以确保自己必胜的数。